package _35_数组中的逆序对;
/*
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字

数据范围：

	对于%50的数据,size<=10^4

	对于%75的数据,size<=10^5

	对于%100的数据,size<=2*10^5

示例1
输入
复制
1,2,3,4,5,6,7,0
输出
复制
7
 */

import java.util.Arrays;

/**
 * 思路：：
 *      用归并排序思想，先拆分成单个数，在归并时，统计逆序对,从两个有序数组的末尾开始算，当A数组的末尾大于B数组的末尾时，count+=B的全部
 *
 *
 *
 */
public class Solution {
    public int InversePairs(int [] array) {
        int tmp[] = new int[array.length];
        return mergeSort(array,tmp,0,array.length-1);
    }

    //合并两个有序的数组，返回逆序对的个数
    int merge(int nums[],int tmp[],int start,int mid,int end){
        int k=end;
        int i=mid;
        int j = end;
        int count=0;
        while(i>=start&&j>mid){
            //当当A数组的末尾大于B数组的末尾时，count+=B的全部
            if(nums[i]>nums[j]){
                count += j-mid;
                tmp[k--] = nums[i--];

                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }
            //否则赋值B
            else{
                tmp[k--] = nums[j--];
            }
        }
        while(i>=start){
            tmp[k--] = nums[i--];
        }
        while(j>mid){
            tmp[k--] = nums[j--];
        }
        for(int m=start;m<=end;m++){
            nums[m] = tmp[m];
        }
        return count;
    }

    int mergeSort(int nums[],int tmp[],int left,int right){
        if(left<right){
            int mid = left +(right-left)/2;
            int leftCount = mergeSort(nums,tmp,left,mid);
            int rightCount = mergeSort(nums,tmp,mid+1,right);
            return (leftCount+rightCount+merge(nums,tmp,left,mid,right))%1000000007;
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int nums[] = {1,2,3,4,5,6,7,0};
        System.out.println(solution.InversePairs(nums));
        Arrays.stream(nums).forEach(System.out::print);
    }
}
